package com.wang.sort2;

/**
 * @Author: along
 * @Create: 2021/4/20
 * @Description:返回最大二叉搜索子树的头
 */
public class Demo18_MaxSubBSTHead {
    public static class Node{
        public int value;
        public Node right;
        public Node left;

        public Node(int value) {
            this.value = value;
        }
    }
    //包装子树需要返回给头的信息
    public static class Info{
        public Node maxSubBSTHead;
        public int maxSubBSTSize;
        public int min;
        public int max;

        public Info(Node maxSubBSTHead, int maxSubBSTSize, int min, int max) {
            this.maxSubBSTHead = maxSubBSTHead;
            this.maxSubBSTSize = maxSubBSTSize;
            this.min = min;
            this.max = max;
        }
    }
    //递归
    public static Info process(Node head) {
        if(head == null) {
            return null;//返回值不好确定时，直接返回null，在下面调用时需要自己判空
        }
        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);

        Node maxSubBSTHead = null;
        int maxSubBSTSize = 0;
        int min = head.value;
        int max = head.value;
        if(leftInfo != null) {
            min = Math.min(min, leftInfo.min);
            max = Math.max(max, leftInfo.max);
            maxSubBSTHead = leftInfo.maxSubBSTHead;
            maxSubBSTSize = leftInfo.maxSubBSTSize;
        }
        if(rightInfo != null) {
            min = Math.min(min, rightInfo.min);
            max = Math.max(max, rightInfo.max);
            if(rightInfo.maxSubBSTSize > maxSubBSTSize) {
                maxSubBSTSize = rightInfo.maxSubBSTSize;
                maxSubBSTHead = rightInfo.maxSubBSTHead;
            }
        }
        if((leftInfo == null ? true : (leftInfo.maxSubBSTHead == maxSubBSTHead && leftInfo.max < head.value))
                &&(rightInfo == null ? true : (rightInfo.maxSubBSTHead == maxSubBSTHead && rightInfo.min > head.value))) {
                maxSubBSTHead = head;
                maxSubBSTSize = (leftInfo == null ? 0 : leftInfo.maxSubBSTSize) + (rightInfo == null ? 0 : rightInfo.maxSubBSTSize) + 1;
        }
        return new Info(maxSubBSTHead,maxSubBSTSize,min,max);
    }
}
